A Fast and Effective Algorithm for the Feedback Arc Set Problem

A divide-and-conquer approach for the feedback arc set is presented. The divide step is performed by solving a minimum bisection problem. Two strategies are used to solve minimum bisection problem: A heuristic based on the stochastic evolution methodology, and a heuristic based on dynamic clustering. Empirical results are presented to compare our method with other approaches. An algorithm to construct test cases for the feedback arc set problem with known optimal number of feedback arcs, is also presented.     

涡轮叶片的解析成型与优化设计方法

本文发展了一种对于涡轮叶片用任意圆锥曲线作为基本曲线实现几何成型的解析方法,大量试算表明,该方法可以适应相当大一部分涡轮叶片几何造型的需要．本文还用正反问题相结合的方法对实用中的涡轮叶片进行改型优化,取得了较好效果,Ｎ－Ｓ流场分析表明,改型后的新叶栅比原叶栅性能有明显改善．     

Simplicial Vertices in Graphs with no Induced Four‐Edge Path or Four‐Edge Antipath,and the H6‐Conjecture

Let be the class of all graphs with no induced four‐edge path or four‐edge antipath. Hayward and Nastos 6 conjectured that every prime graph in not isomorphic to the cycle of length five is either a split graph or contains a certain useful arrangement of simplicial and antisimplicial vertices. In this article, we give a counterexample to their conjecture, and prove a slightly weaker version. Additionally, applying a result of the first author and Seymour 1 we give a short proof of Fouquet's result 3 on the structure of the subclass of bull‐free graphs contained in .     

On Estimating the Cumulant Generating Function of Linear Processes

We compare two estimates of the cumulant generating function of a stationary linear process. The first estimate is based on the empirical moment generating function. The second estimate uses the linear representation of the process and the empirical moment generating function of the innovations. Asymptotic expressions for the mean square errors are derived under short- and long-range dependence. For long-memory processes, the estimate based on the linear representation turns out to have a better rate of convergence. Thus, exploiting the linear structure of the process leads to an infinite gain in asymptotic efficiency.     

A vertex incremental approach for maintaining chordality

For a chordal graph G=(V,E), we study the problem of whether a new vertex u∉V and a given set of edges between u and vertices in V can be added to G so that the resulting graph remains chordal. We show how to resolve this efficiently, and at the same time, if the answer is no, specify a maximal subset of the proposed edges that can be added along with u, or conversely, a minimal set of extra edges that can be added in addition to the given set, so that the resulting graph is chordal. In order to do this, we give a new characterization of chordal graphs and, for each potential new edge uv, a characterization of the set of edges incident to u that also must be added to G along with uv. We propose a data structure that can compute and add each such set in O(n) time. Based on these results, we present an algorithm that computes both a minimal triangulation and a maximal chordal subgraph of an arbitrary input graph in O(nm) time, using a totally new vertex incremental approach. In contrast to previous algorithms, our process is on-line in that each new vertex is added without reconsidering any choice made at previous steps, and without requiring any knowledge of the vertices that might be added subsequently.     

Explicit bounds for multidimensional linear recurrences with restricted coefficients

This note employs path counting techniques to extend recent results on bounds for odd order linear recurrences to higher dimensions. The results imply optimal zero-free polydisks for multivariable power series with 0, 1 coefficients. Among the applications is a result that states that the optimal zero-free polydisk has radius approximately 1/(v+1), for large dimensions v.     

First-order definability and algebraicity of the sets of annihilating and generating collections of elements for some relatively free solvable groups

We study the first-order definable, Diophantine, and algebraic subsets in the set of all ordered sets generating a group or generating a group as a normal subgroup for some relatively free solvable groups.     

行和列和为常量的(0,1)-矩阵的计数

Let fs,t(m,n) be the number of (0,1) - matrices of size m x n such that each row has exactly s ones and each column has exactly t ones (sm = nt). How to determine fs,t(m,n)? As R. P. Stanley has observed (Enumerative CombinatoricsⅠ(1997), Example 1.1.3), the determination of fs,t(m, n) is an unsolved problem, except for very small s, t. In this paper the closed formulas for f2,2(n,n), f3,2(m,n), f4,2(m,n) are given. And recursion formulas and generating functions are discussed.